package com.evan.review.basic.collection;

import android.os.Bundle;
import android.widget.TextView;
import androidx.appcompat.app.AppCompatActivity;
import com.evan.review.R;
import java.util.TreeMap;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.SortedMap;
import java.util.Comparator;

/**
 * TreeMap详解Activity
 * 
 * 本Activity详细介绍TreeMap的实现原理、特性和使用方法：
 * 1. TreeMap的底层数据结构与实现
 * 2. TreeMap常用操作与性能分析
 * 3. TreeMap、HashMap的对比
 * 4. TreeMap的导航方法与排序方式
 * 5. TreeMap面试题与应用场景
 */
public class TreeMapActivity extends AppCompatActivity {
    
    private TextView tvOutput;
    
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_data_structure);
        
        setTitle("TreeMap详解");
        
        tvOutput = findViewById(R.id.tv_output);
        
        // 展示TreeMap基本原理
        demonstrateTreeMapPrinciple();
        
        // 展示TreeMap基本操作
        demonstrateTreeMapOperations();
        
        // 展示TreeMap导航方法
        demonstrateTreeMapNavigation();
        
        // 展示TreeMap自定义排序
        demonstrateTreeMapCustomSorting();
        
        // 展示TreeMap与HashMap比较
        demonstrateComparisonWithHashMap();
        
        // 展示TreeMap常见面试题
        demonstrateInterviewQuestions();
    }
    
    /**
     * 展示TreeMap的基本原理
     */
    private void demonstrateTreeMapPrinciple() {
        StringBuilder output = new StringBuilder();
        output.append("=== TreeMap底层原理 ===\n\n");
        
        // 1. 底层实现
        output.append("1. 底层实现：\n");
        output.append("• TreeMap基于红黑树（Red-Black Tree）实现\n");
        output.append("• 红黑树是一种自平衡的二叉查找树\n");
        output.append("• 红黑树特性：\n");
        output.append("  - 每个节点要么是红色，要么是黑色\n");
        output.append("  - 根节点是黑色\n");
        output.append("  - 所有叶子节点（NIL节点）是黑色\n");
        output.append("  - 红色节点的两个子节点都是黑色\n");
        output.append("  - 从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点\n\n");
        
        // 2. 实现的接口
        output.append("2. 实现的接口：\n");
        output.append("• NavigableMap: 提供了导航方法\n");
        output.append("• SortedMap: 保证键的有序性\n");
        output.append("• Map: 基本的键值对操作\n");
        output.append("• Cloneable: 支持克隆\n");
        output.append("• Serializable: 支持序列化\n\n");
        
        // 3. 核心特性
        output.append("3. 核心特性：\n");
        output.append("• 键有序：按键的自然顺序或自定义Comparator排序\n");
        output.append("• 不允许null键（会抛出NullPointerException），但允许null值\n");
        output.append("• 非线程安全\n");
        output.append("• 提供了丰富的导航方法\n");
        output.append("• 基本操作（get、put、remove、containsKey）的时间复杂度为O(log n)\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示TreeMap基本操作
     */
    private void demonstrateTreeMapOperations() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== TreeMap基本操作 ===\n\n");
        
        // 创建TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        
        // 1. 添加元素
        output.append("1. 添加元素：\n");
        output.append("TreeMap<String, Integer> treeMap = new TreeMap<>();\n");
        output.append("treeMap.put(\"C\", 3);      // 添加键值对, O(log n)\n");
        treeMap.put("C", 3);
        output.append("treeMap.put(\"A\", 1);      // 添加键值对, O(log n)\n");
        treeMap.put("A", 1);
        output.append("treeMap.put(\"B\", 2);      // 添加键值对, O(log n)\n");
        treeMap.put("B", 2);
        output.append("treeMap.put(\"D\", 4);      // 添加键值对, O(log n)\n");
        treeMap.put("D", 4);
        output.append("// 当前treeMap: " + treeMap + " (按键的自然顺序排序)\n\n");
        
        // 2. 获取元素
        output.append("2. 获取元素：\n");
        output.append("treeMap.get(\"A\");         // 返回 1, O(log n)\n");
        output.append("treeMap.getOrDefault(\"E\", 0); // 返回 0（默认值）, O(log n)\n");
        output.append("treeMap.containsKey(\"B\"); // 检查键是否存在, 返回 true, O(log n)\n");
        output.append("treeMap.containsValue(5);  // 检查值是否存在, 返回 false, O(n)\n\n");
        
        // 3. 删除元素
        output.append("3. 删除元素：\n");
        output.append("treeMap.remove(\"A\");      // 删除键为A的元素, O(log n)\n");
        treeMap.remove("A");
        output.append("// 当前treeMap: " + treeMap + "\n\n");
        
        // 4. 遍历方式
        output.append("4. 遍历方式：\n");
        output.append("// 方式1: 遍历键值对\n");
        output.append("for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {\n");
        output.append("    System.out.println(entry.getKey() + \": \" + entry.getValue());\n");
        output.append("}\n\n");
        
        output.append("// 方式2: 遍历键\n");
        output.append("for (String key : treeMap.keySet()) {\n");
        output.append("    System.out.println(key + \": \" + treeMap.get(key));\n");
        output.append("}\n\n");
        
        output.append("// 方式3: 使用forEach (Java 8+)\n");
        output.append("treeMap.forEach((key, value) -> System.out.println(key + \": \" + value));\n\n");
        
        // 5. 其他基本操作
        output.append("5. 其他基本操作：\n");
        output.append("treeMap.size();            // 返回元素数量: " + treeMap.size() + "\n");
        output.append("treeMap.isEmpty();         // 检查是否为空: " + treeMap.isEmpty() + "\n");
        output.append("treeMap.clear();           // 清空所有元素\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示TreeMap导航方法
     */
    private void demonstrateTreeMapNavigation() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== TreeMap导航方法 ===\n\n");
        
        // 1. 创建TreeMap并添加数据
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "Ten");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");
        
        output.append("// 创建TreeMap并填充数据\n");
        output.append("TreeMap<Integer, String> map = new TreeMap<>();\n");
        output.append("map.put(10, \"Ten\");\n");
        output.append("map.put(20, \"Twenty\");\n");
        output.append("map.put(30, \"Thirty\");\n");
        output.append("map.put(40, \"Forty\");\n");
        output.append("map.put(50, \"Fifty\");\n");
        output.append("// 当前map: " + map + "\n\n");
        
        // 2. 获取第一个和最后一个元素
        output.append("2. 获取第一个和最后一个元素：\n");
        output.append("map.firstKey();           // 返回最小键: " + map.firstKey() + "\n");
        output.append("map.lastKey();            // 返回最大键: " + map.lastKey() + "\n");
        output.append("map.firstEntry();         // 返回最小键的键值对: " + map.firstEntry() + "\n");
        output.append("map.lastEntry();          // 返回最大键的键值对: " + map.lastEntry() + "\n\n");
        
        // 3. 获取给定键的前后键
        output.append("3. 获取给定键的前后键：\n");
        output.append("map.lowerKey(30);         // 返回<30的最大键: " + map.lowerKey(30) + "\n");
        output.append("map.higherKey(30);        // 返回>30的最小键: " + map.higherKey(30) + "\n");
        output.append("map.floorKey(25);         // 返回<=25的最大键: " + map.floorKey(25) + "\n");
        output.append("map.ceilingKey(25);       // 返回>=25的最小键: " + map.ceilingKey(25) + "\n\n");
        
        output.append("map.lowerEntry(30);       // 返回<30的最大键的键值对: " + map.lowerEntry(30) + "\n");
        output.append("map.higherEntry(30);      // 返回>30的最小键的键值对: " + map.higherEntry(30) + "\n");
        output.append("map.floorEntry(25);       // 返回<=25的最大键的键值对: " + map.floorEntry(25) + "\n");
        output.append("map.ceilingEntry(25);     // 返回>=25的最小键的键值对: " + map.ceilingEntry(25) + "\n\n");
        
        // 4. 获取并移除元素
        output.append("4. 获取并移除元素：\n");
        Map.Entry<Integer, String> entry = map.pollFirstEntry();
        output.append("map.pollFirstEntry();     // 删除并返回最小键的键值对: " + entry + "\n");
        entry = map.pollLastEntry();
        output.append("map.pollLastEntry();      // 删除并返回最大键的键值对: " + entry + "\n");
        output.append("// 当前map: " + map + "\n\n");
        
        // 5. 获取子Map
        output.append("5. 获取子Map：\n");
        output.append("// 范围查询\n");
        SortedMap<Integer, String> subMap1 = map.subMap(20, 40);
        output.append("map.subMap(20, 40);       // 返回键在[20,40)范围的子Map: " + subMap1 + "\n");
        
        NavigableMap<Integer, String> subMap2 = map.subMap(20, true, 40, false);
        output.append("map.subMap(20, true, 40, false); // 包含端点控制: " + subMap2 + "\n");
        
        SortedMap<Integer, String> headMap = map.headMap(30);
        output.append("map.headMap(30);          // 返回键<30的子Map: " + headMap + "\n");
        
        NavigableMap<Integer, String> headMapInc = map.headMap(30, true);
        output.append("map.headMap(30, true);    // 返回键<=30的子Map: " + headMapInc + "\n");
        
        SortedMap<Integer, String> tailMap = map.tailMap(30);
        output.append("map.tailMap(30);          // 返回键>=30的子Map: " + tailMap + "\n");
        
        NavigableMap<Integer, String> tailMapExc = map.tailMap(30, false);
        output.append("map.tailMap(30, false);   // 返回键>30的子Map: " + tailMapExc + "\n\n");
        
        // 6. 逆序视图
        output.append("6. 逆序视图：\n");
        NavigableMap<Integer, String> descendingMap = map.descendingMap();
        output.append("map.descendingMap();      // 返回逆序视图: " + descendingMap + "\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示TreeMap自定义排序
     */
    private void demonstrateTreeMapCustomSorting() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== TreeMap自定义排序 ===\n\n");
        
        // 1. 默认排序（自然顺序）
        output.append("1. 默认排序（自然顺序）：\n");
        output.append("// 默认按键的自然顺序排序\n");
        output.append("TreeMap<String, Integer> defaultMap = new TreeMap<>();\n");
        output.append("defaultMap.put(\"apple\", 1);\n");
        output.append("defaultMap.put(\"pear\", 2);\n");
        output.append("defaultMap.put(\"banana\", 3);\n");
        
        TreeMap<String, Integer> defaultMap = new TreeMap<>();
        defaultMap.put("apple", 1);
        defaultMap.put("pear", 2);
        defaultMap.put("banana", 3);
        output.append("// 结果（字母顺序）: " + defaultMap + "\n\n");
        
        // 2. 自定义比较器（按字符串长度排序）
        output.append("2. 自定义比较器（按字符串长度排序）：\n");
        output.append("// 使用Comparator自定义排序\n");
        output.append("TreeMap<String, Integer> lengthMap = new TreeMap<>((s1, s2) -> {\n");
        output.append("    // 按字符串长度比较\n");
        output.append("    int lenCompare = Integer.compare(s1.length(), s2.length());\n");
        output.append("    // 如果长度相同，按字母顺序比较\n");
        output.append("    return lenCompare != 0 ? lenCompare : s1.compareTo(s2);\n");
        output.append("});\n");
        
        TreeMap<String, Integer> lengthMap = new TreeMap<>((s1, s2) -> {
            // 按字符串长度比较
            int lenCompare = Integer.compare(s1.length(), s2.length());
            // 如果长度相同，按字母顺序比较
            return lenCompare != 0 ? lenCompare : s1.compareTo(s2);
        });
        
        lengthMap.put("apple", 1);
        lengthMap.put("pear", 2);
        lengthMap.put("banana", 3);
        
        output.append("lengthMap.put(\"apple\", 1);\n");
        output.append("lengthMap.put(\"pear\", 2);\n");
        output.append("lengthMap.put(\"banana\", 3);\n");
        output.append("// 结果（按字符串长度排序）: " + lengthMap + "\n\n");
        
        // 3. 自定义比较器（反向排序）
        output.append("3. 自定义比较器（反向排序）：\n");
        output.append("// 使用reverseOrder获取反向比较器\n");
        output.append("TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());\n");
        
        TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
        reverseMap.put("apple", 1);
        reverseMap.put("pear", 2);
        reverseMap.put("banana", 3);
        
        output.append("reverseMap.put(\"apple\", 1);\n");
        output.append("reverseMap.put(\"pear\", 2);\n");
        output.append("reverseMap.put(\"banana\", 3);\n");
        output.append("// 结果（反向字母顺序）: " + reverseMap + "\n\n");
        
        // 4. 自定义对象排序
        output.append("4. 自定义对象作为键：\n");
        output.append("// 方式1：让类实现Comparable接口\n");
        output.append("class Person implements Comparable<Person> {\n");
        output.append("    private String name;\n");
        output.append("    private int age;\n\n");
        
        output.append("    // 实现compareTo方法\n");
        output.append("    @Override\n");
        output.append("    public int compareTo(Person other) {\n");
        output.append("        return Integer.compare(this.age, other.age);\n");
        output.append("    }\n");
        output.append("}\n\n");
        
        output.append("// 方式2：提供外部Comparator\n");
        output.append("TreeMap<Person, String> personMap = new TreeMap<>((p1, p2) -> {\n");
        output.append("    // 先按年龄比较\n");
        output.append("    int ageCompare = Integer.compare(p1.getAge(), p2.getAge());\n");
        output.append("    // 如果年龄相同，按姓名比较\n");
        output.append("    return ageCompare != 0 ? ageCompare : p1.getName().compareTo(p2.getName());\n");
        output.append("});\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示TreeMap与HashMap比较
     */
    private void demonstrateComparisonWithHashMap() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== TreeMap与HashMap比较 ===\n\n");
        
        // 1. 性能比较
        output.append("1. 性能比较：\n");
        output.append("┌───────────────────┬─────────────┬─────────────┐\n");
        output.append("│ 操作              │ HashMap     │ TreeMap     │\n");
        output.append("├───────────────────┼─────────────┼─────────────┤\n");
        output.append("│ put/get/remove    │ O(1)        │ O(log n)    │\n");
        output.append("│ containsKey       │ O(1)        │ O(log n)    │\n");
        output.append("│ containsValue     │ O(n)        │ O(n)        │\n");
        output.append("│ 内存占用          │ 较少        │ 较多        │\n");
        output.append("│ 迭代元素顺序      │ 无序        │ 有序        │\n");
        output.append("└───────────────────┴─────────────┴─────────────┘\n\n");
        
        // 2. 功能对比
        output.append("2. 功能对比：\n");
        output.append("┌───────────────────┬─────────────────┬─────────────────┐\n");
        output.append("│ 特性              │ HashMap         │ TreeMap         │\n");
        output.append("├───────────────────┼─────────────────┼─────────────────┤\n");
        output.append("│ 有序性            │ 无序            │ 键有序          │\n");
        output.append("│ null键            │ 允许            │ 不允许          │\n");
        output.append("│ null值            │ 允许            │ 允许            │\n");
        output.append("│ 导航方法          │ 不支持          │ 支持            │\n");
        output.append("│ 比较方式          │ hashCode/equals │ compareTo       │\n");
        output.append("│ 底层实现          │ 哈希表          │ 红黑树          │\n");
        output.append("└───────────────────┴─────────────────┴─────────────────┘\n\n");
        
        // 3. 适用场景
        output.append("3. 适用场景：\n");
        output.append("• HashMap适合：\n");
        output.append("  - 不关心键的顺序\n");
        output.append("  - 性能是首要考虑因素\n");
        output.append("  - 需要允许null键\n");
        output.append("  - 键不需要比较，只需要相等性检查\n\n");
        
        output.append("• TreeMap适合：\n");
        output.append("  - 需要按键排序\n");
        output.append("  - 需要获取有序的键集合\n");
        output.append("  - 需要使用范围查询（如：范围搜索、最近邻搜索）\n");
        output.append("  - 需要按某种顺序迭代键值对\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示TreeMap常见面试题
     */
    private void demonstrateInterviewQuestions() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== TreeMap面试题 ===\n\n");
        
        // 1. TreeMap底层实现
        output.append("1. TreeMap的底层实现原理是什么？\n");
        output.append("答：TreeMap基于红黑树实现：\n");
        output.append("• 红黑树是一种自平衡的二叉查找树，保证最坏情况下的时间复杂度为O(log n)\n");
        output.append("• 红黑树通过节点的颜色（红/黑）属性以及一系列规则保持平衡\n");
        output.append("• 平衡规则保证树的最长路径不超过最短路径的两倍\n");
        output.append("• 插入和删除操作可能需要旋转和重新着色操作来维持红黑树性质\n\n");
        
        // 2. TreeMap和HashMap的主要区别
        output.append("2. TreeMap和HashMap的主要区别？\n");
        output.append("答：主要区别包括：\n");
        output.append("• 有序性：TreeMap保持键的有序（自然顺序或自定义顺序）；HashMap无序\n");
        output.append("• 性能：HashMap操作复杂度O(1)；TreeMap操作复杂度O(log n)\n");
        output.append("• 内存占用：TreeMap需要存储节点颜色和指针，占用更多内存\n");
        output.append("• 功能：TreeMap提供了导航方法（如floorKey, ceilingKey等）\n");
        output.append("• 键的限制：TreeMap不允许null键；HashMap允许一个null键\n");
        output.append("• 底层实现：TreeMap基于红黑树；HashMap基于哈希表（数组+链表/红黑树）\n\n");
        
        // 3. TreeMap排序原理
        output.append("3. TreeMap如何对键进行排序？\n");
        output.append("答：TreeMap有两种排序方式：\n");
        output.append("• 自然排序：键类需实现Comparable接口，TreeMap使用compareTo方法比较\n");
        output.append("• 自定义排序：在构造函数中提供Comparator实现\n");
        output.append("• 排序决定了键在红黑树中的位置，进而影响查找、插入和删除操作\n");
        output.append("• 排序一旦确定，不能更改。如需不同排序，需创建新的TreeMap\n\n");
        
        // 4. TreeMap的使用场景
        output.append("4. TreeMap的典型应用场景有哪些？\n");
        output.append("答：典型应用场景包括：\n");
        output.append("• 需要按键排序的场景：如日程表（时间作为键）\n");
        output.append("• 范围查询：如查找3月至5月的所有事件\n");
        output.append("• 最近邻搜索：如查找小于等于某个键的最大键（floorKey）\n");
        output.append("• 字典、词典实现：按字母顺序存储和查找\n");
        output.append("• 优先级任务队列：按优先级（键）排序的任务\n");
        output.append("• 排行榜：按分数排序的玩家列表\n\n");
        
        // 5. TreeMap与TreeSet的关系
        output.append("5. TreeMap与TreeSet有什么关系？\n");
        output.append("答：它们的关系类似于HashMap与HashSet：\n");
        output.append("• TreeSet内部使用TreeMap实现\n");
        output.append("• TreeSet的元素存储为TreeMap的键\n");
        output.append("• TreeMap的值都是同一个Object常量\n");
        output.append("• TreeSet继承了TreeMap的性能特点和排序特性\n");
        output.append("• 选择：需要存储键值对用TreeMap，只需要存储有序不重复元素用TreeSet\n\n");
        
        // 6. 线程安全问题
        output.append("6. TreeMap是线程安全的吗？如何实现线程安全？\n");
        output.append("答：TreeMap不是线程安全的。线程安全解决方案：\n");
        output.append("• 使用Collections.synchronizedSortedMap包装：\n");
        output.append("  SortedMap<K,V> syncMap = Collections.synchronizedSortedMap(new TreeMap<>());\n");
        output.append("• 使用并发集合（但没有保留排序特性）：\n");
        output.append("  ConcurrentHashMap或ConcurrentSkipListMap\n");
        output.append("• 使用显式锁或同步块：\n");
        output.append("  synchronized(map) { map.put(key, value); }\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 更新输出文本
     */
    private void updateOutput(String text) {
        tvOutput.append(text);
    }
} 